DROPS

Document

DOI: 10.4230/LIPIcs.TQC.2013.20

Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem

Authors: Greg Kuperberg

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)

Abstract

We give an algorithm for the hidden subgroup problem for the dihedral group D_N, or equivalently the cyclic hidden shift problem, that supersedes our first algorithm and is suggested by Regev's algorithm. It runs in exp(O(sqrt(log N))) quantum time and uses exp(O(sqrt(log N))) classical space, but only O(log N) quantum space. The algorithm also runs faster with quantumly addressable classical space than with fully classical space. In the hidden shift form, which is more natural for this algorithm regardless, it can also make use of multiple hidden shifts. It can also be extended with two parameters that trade classical space and classical time for quantum time. At the extreme space-saving end, the algorithm becomes Regev's algorithm. At the other end, if the algorithm is allowed classical memory with quantum random access, then many trade-offs between classical and quantum time are possible.

Cite as

Greg Kuperberg. Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 20-34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{kuperberg:LIPIcs.TQC.2013.20,
  author =	{Kuperberg, Greg},
  title =	{{Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{20--34},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.20},
  URN =		{urn:nbn:de:0030-drops-43213},
  doi =		{10.4230/LIPIcs.TQC.2013.20},
  annote =	{Keywords: quantum algorithm, hidden subgroup problem, sieve, subexponential time}
}

Search Results

Documents authored by Kuperberg, Greg

Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message